package com.sgx.learning.luban.arithmetic.sort;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5,3,10,22,1};
        sort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr,int left,int right) {
        if(right > left) {
            int mid = (left + right) / 2;
            sort(arr,left,mid);
            sort(arr,mid + 1,right);
            merge(arr,left,mid,right);
        }
    }

    private static void merge(int[] arr,int left,int mid, int right) {
        int[] temp = new int[arr.length];
        int pointL = left;
        int pointR = mid + 1;
        int loc = left;
        while(pointL <= mid && pointR <= right) {
            if(arr[pointL] <= arr[pointR]) {
                temp[loc] = arr[pointL];
                loc++;
                pointL++;
            } else {
                temp[loc] = arr[pointR];
                loc++;
                pointR++;
            }
        }
        while(pointL <= mid) {
            temp[loc] = arr[pointL];
            pointL++;
            loc++;
        }
        while(pointR <= right) {
            temp[loc] = arr[pointR];
            loc++;
            pointR++;
        }
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }
}
